W13. Planarity and Coloring

1. Theory

1.1 Planar Graphs

1.1.1 Definition of Planar Graphs

A planar graph is a graph that can be drawn on a flat surface (a plane) in such a way that no edges cross each other, except at their endpoints (vertices). This special drawing is called a plane embedding (or planar embedding) of the graph.

The key insight is that a graph being planar is an intrinsic property of the graph itself—it doesn’t matter how the graph is initially drawn. If you can somehow redraw it without crossings, then it’s planar. Many graphs that appear to have crossing edges can actually be redrawn to eliminate those crossings.

For example, the complete graph (4 vertices where every vertex connects to every other) can be drawn as a square with both diagonals, but it can also be drawn as a triangle with one vertex in the center—both are valid plane embeddings with no crossings.

1.1.2 Examples of Planar and Non-Planar Graphs

Complete Graphs :

The complete graph has vertices where every pair of vertices is connected by an edge.

• : Two vertices connected by one edge — planar
• : A triangle — planar
• : A tetrahedron graph — planar (can be drawn as a triangle with a central vertex)
• : Five vertices, each connected to all others — NOT planar
• , , …: All NOT planar (they contain as a subgraph)

Complete Bipartite Graphs :

The complete bipartite graph has two sets of vertices (of sizes and ) where every vertex in one set connects to every vertex in the other set.

• : planar
• : planar
• for any : planar (can always be drawn without crossings)
• : NOT planar (known as the “utility graph” or “three houses, three utilities” problem)
• , , …: All NOT planar (they contain as a subgraph)

1.2 Euler’s Formula

1.2.1 Faces of a Plane Graph

When a planar graph is drawn on a plane without crossings, it divides the plane into regions called faces. A face is a region bounded by edges. This includes:

• Interior faces: The bounded regions enclosed by edges
• Exterior face (or infinite face): The unbounded region outside the graph

For example, a triangle drawn on a plane has exactly 2 faces: one interior face (the region inside the triangle) and one exterior face (everything outside).

1.2.2 Euler’s Formula Statement and Proof

Euler’s Formula is a fundamental relationship for connected planar graphs:

where:

• = number of vertices
• = number of edges
• = number of faces (including the exterior face)

Proof by Induction on the Number of Faces:

Base Case (): If the graph has only one face (the exterior face), then the graph contains no cycles—it must be a tree. For a tree with vertices, we have edges. Therefore: . ✓

Inductive Step: Assume the formula holds for all plane embeddings with fewer than faces, where .

Consider a plane embedding with faces. Since there are at least 2 faces, there must be at least one cycle in the graph. Let be an edge that lies on some cycle.

When we remove this edge , the graph remains connected (because the edge was part of a cycle, so there’s still an alternative path). The plane embedding has faces, because removing edge merges the two faces that were on either side of it into one face.

By the induction hypothesis:

Since (same vertices) and (one fewer edge):

Thus, Euler’s formula holds. ∎

1.2.3 Euler’s Formula for Convex Polyhedra

Euler’s formula also applies to convex polyhedra (3D shapes with flat faces). The surface of any convex polyhedron can be “flattened” into a planar graph, so:

where = vertices, = edges, = faces of the polyhedron.

Examples with the five Platonic solids:

• Tetrahedron: , , → ✓
• Cube (Hexahedron): , , → ✓
• Octahedron: , , → ✓
• Dodecahedron: , , → ✓
• Icosahedron: , , → ✓

1.3 Corollaries of Euler’s Formula

1.3.1 Edge Bound for Planar Graphs

Corollary 1: If is a planar graph with vertices, then:

Proof: Each face is bounded by at least 3 edges (since a face must form a cycle of at least length 3). Each edge can border at most 2 faces. Therefore:

From Euler’s formula, : ∎

Important: This is a necessary condition for planarity, not a sufficient one. A graph can satisfy and still be non-planar!

1.3.2 Proving is Non-Planar

Corollary 2: is not planar.

Proof: For : and .

If were planar, then by Corollary 1:

But is false. Contradiction! Therefore, is not planar. ∎

1.3.3 Proving is Non-Planar

Corollary 3: is not planar.

Note: We cannot use Corollary 1 directly here. For : , , and is true! So we need a different approach.

Proof: For : , .

If were planar, by Euler’s formula: faces.

Since is a bipartite graph, it contains no odd cycles. In particular, it has no triangles. Therefore, every face must be bounded by at least 4 edges (not 3).

So: , which gives us , i.e., .

This is false! Contradiction. Therefore, is not planar. ∎

1.4 Kuratowski’s Theorem

1.4.1 Subdivision of a Graph

An edge is subdivided when it is replaced by a path by introducing a new vertex in the middle of the edge. A subdivision of a graph is any graph obtained from by performing a sequence of such edge subdivisions.

Intuitively, subdividing an edge just adds a “bend point” in the middle of an edge—it doesn’t fundamentally change the structure of the graph.

Key Lemma: A graph is planar if and only if all of its subdivisions are planar.

This makes sense: adding points along edges doesn’t create or remove crossings.

1.4.2 Kuratowski’s Theorem Statement

Kuratowski’s Theorem provides a complete characterization of planar graphs:

A graph is planar if and only if it does not contain a subgraph that is a subdivision of or .

In other words:

• If you can find a subdivision of or hiding inside your graph, then the graph is NOT planar
• If no such subdivision exists, then the graph IS planar

This theorem tells us that and are the “minimal” non-planar graphs—every non-planar graph must contain one of them (or their subdivisions) as a subgraph.

1.5 Graph Colourings

1.5.1 Definition of Graph Colouring

A -colouring of a graph is an assignment of “colours” (typically represented by integers ) to the vertices of . Formally, it’s a function:

A colouring is called proper if no two adjacent vertices have the same colour. That is, for every edge , we have .

A graph is -colourable if there exists a proper -colouring for .

1.5.2 Chromatic Number

The chromatic number of a graph is the minimum number of colours needed to properly colour the graph:

Special cases:

• if and only if (empty graph)
• if and only if has no edges (null graph )
• (complete graph requires colours since every vertex is adjacent to every other)

1.5.3 The Four Colour Theorem

Four Colour Theorem: Every planar graph is 4-colourable.

This famous theorem states that for any planar graph . This means any map can be coloured with at most 4 colours such that no two adjacent regions share the same colour.

1.5.4 Bipartite Graphs and 2-Colouring

Theorem: The following are equivalent:

2. is a non-trivial bipartite graph
3. All cycles in have even length

This means a graph can be 2-coloured (using just two colours) if and only if it contains no odd-length cycles. This is because in a bipartite graph, we can colour one partition with one colour and the other partition with another colour.

1.6 Graph Searching Algorithms

1.6.1 Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

Algorithm:

1. Start at an arbitrary vertex (mark it as visited)
2. From the current vertex, move to an unvisited adjacent vertex
3. Repeat step 2 until no unvisited adjacent vertices exist
4. Backtrack to the previous vertex and try other unvisited neighbors
5. Continue until all reachable vertices are visited

DFS explores “deep” into the graph first, only backtracking when it reaches a dead end.

1.6.2 Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors at the current depth level before moving to vertices at the next depth level.

Algorithm:

1. Start at an arbitrary vertex (mark it as visited)
2. Visit all unvisited neighbors of the current vertex
3. Move to the next “level” and visit all unvisited neighbors of those vertices
4. Continue level by level until all reachable vertices are visited

BFS explores the graph in “layers” or “waves” emanating from the starting vertex.

Application: BFS can be used to prove that a graph is bipartite (2-colourable). If during BFS traversal we can assign alternating colours to successive levels without conflicts, the graph is bipartite.

---

2. Definitions

• Planar Graph: A graph that can be drawn on a plane without any edges crossing except at their endpoints.
• Plane Embedding: A specific drawing of a planar graph on a plane with no edge crossings.
• Face: A region bounded by edges in a plane embedding, including the unbounded exterior face.
• Exterior Face (Infinite Face): The unbounded region outside all edges in a plane embedding.
• Subdivision: A graph obtained by replacing edges with paths through new intermediate vertices.
• -Colouring: An assignment of colours to the vertices of a graph.
• Proper Colouring: A colouring where no two adjacent vertices share the same colour.
• -Colourable: A graph that admits a proper -colouring.
• Chromatic Number : The minimum number of colours needed to properly colour graph .
• Depth-First Search (DFS): A graph traversal that explores as far as possible along each branch before backtracking.
• Breadth-First Search (BFS): A graph traversal that explores all vertices at the current depth before moving to the next depth level.
• Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.

---

3. Formulas

• Euler’s Formula (Planar Graphs): , where = vertices, = edges, = faces
• Edge Bound for Planar Graphs: If is planar with , then
• Edge Bound for Bipartite Planar Graphs: If is a bipartite planar graph with , then
• Face-Edge Inequality (General): (each face has edges, each edge borders faces)
• Face-Edge Inequality (Bipartite): (bipartite graphs have no triangles, so each face has edges)
• Chromatic Number of Complete Graph:
• Chromatic Number of Null Graph: (no edges)
• Chromatic Number of Bipartite Graph: if is a non-trivial bipartite graph
• Chromatic Number of Odd Cycle:
• Chromatic Number of Even Cycle:
• Four Colour Theorem: for any planar graph

---

4. Practice

4.1. Show That Graphs Are Planar (Lab 11, Task 1)

Show (draw) that the following graphs are planar:

Click to see the solution

!addsolution

4.2. Determine Planarity of Two Graphs (Lab 11, Task 2)

Are the following graphs planar? Explain your answer.

Click to see the solution

!addsolution

4.3. Prove is Planar (Lab 11, Task 3)

Prove that is planar for any edge .

Click to see the solution

Key Concept: Removing any edge from reduces it enough to become planar.

1. Properties of :

   • Vertices:
   • Edges:

2. Check edge bound: ✓

   The edge bound is satisfied (exactly at the limit).

3. Construct planar embedding:

   • Label vertices as
   • Without loss of generality, assume edge is removed
   • Draw vertex 1 in the center of a square formed by vertices 2, 3, 4, 5
   • All edges from vertex 1 to 3, 4, 5 can be drawn inside
   • The edges 2-3, 3-4, 4-5, 5-2, 2-4, 3-5 form the outer structure
   • Since edge (1,2) is missing, no crossing occurs

4. Verify no or subdivision exists:

   • cannot contain (it has fewer edges)
   • cannot contain (only 5 vertices, needs 6)

Answer: is planar because it satisfies the edge bound and can be drawn without crossings. The removal of any single edge from eliminates the property that made non-planar.

4.4. Prove is Planar (Lab 11, Task 4)

Prove that is planar for any edge .

Click to see the solution

Key Concept: Removing any edge from breaks the structure that made it non-planar.

1. Properties of :

   • Vertices:
   • Edges:

2. Check edge bound for bipartite graphs: For bipartite graphs (no odd cycles): ✓

   The bound is satisfied exactly.

3. Construct planar embedding:

   • Let the two partitions be and
   • Without loss of generality, remove edge
   • Draw at the top, at the bottom
   • Arrange other vertices to form a planar layout:
     • Place on the left and on the right
     • Draw remaining 8 edges without crossings

4. Why it works:

   • fails the bipartite edge bound:
   • Removing one edge brings it exactly to the boundary
   • The removed edge eliminates the “conflict” that caused non-planarity

Answer: is planar because removing any edge reduces the edge count to exactly satisfy the bipartite planarity bound, and a planar embedding can be constructed.

4.5. Find Chromatic Numbers (Lab 11, Task 5)

Find the chromatic number of the following graphs:

Click to see the solution

!addsolution

4.6. Simple Planarity Check (Tutorial 11, Task 1)

Is the following graph planar? A “diamond” shaped graph with 4 vertices and crossing internal edges.

Click to see the solution

Key Concept: Redraw the graph to eliminate crossings.

1. Original drawing: A diamond with 4 vertices and a vertical and horizontal line through the center, creating crossings.
2. Redraw without crossings:
   • Keep the diamond shape (4 outer edges)
   • One internal edge (say vertical) stays inside
   • The other internal edge (horizontal) is drawn as a curve going around the outside of the diamond

3. Result: The graph can be embedded in the plane without crossings.

Answer: Yes, the graph is planar.

4.7. Planarity of (Tutorial 11, Task 2)

Is the complete bipartite graph planar?

Click to see the solution

Key Concept: graphs are always planar for any .

1. Structure: has 2 vertices in one partition and 3 in another, with all 6 possible edges between partitions.
2. Check edge bound:
   • ,
   • ✓
3. Construct planar embedding:
   • Place one vertex from the first partition (a) at the center
   • Place the other vertex from the first partition (b) outside
   • Arrange the three vertices (c, d, e) of the second partition in a triangle around a
   • Draw edges from a to c, d, e inside the triangle
   • Draw edges from b to c, d, e going around the outside
4. Result: No crossings needed.

Answer: Yes, is planar.

4.8. Planarity of 8-Vertex Grid Graph (Tutorial 11, Task 3)

Is the following graph planar? A graph with 8 vertices in two columns of 4, with many crossing edges.

Click to see the solution

Key Concept: This graph represents a cube’s edge structure, which is planar.

1. Identify the graph: 8 vertices arranged in a 2×4 pattern with specific connections.
2. Recognize as cube graph: The graph is isomorphic to the edge graph of a cube (3-dimensional hypercube ).
3. Construct planar embedding:
   • Draw as a “box within a box” (nested squares)
   • Outer square: vertices 1, 2, 6, 5
   • Inner square: vertices 7, 3, 4, 8
   • Connect corresponding vertices between squares

4. Result: The cube graph is planar.

Answer: Yes, the graph is planar and can be drawn as nested squares.

4.9. Comparing Cube and Modified Cube (Tutorial 11, Task 4)

Which of the following graphs are planar?

• : A standard wireframe cube
• : A cube with an extra diagonal edge and a curved edge connecting opposite corners

Click to see the solution

(Standard cube):

1. The cube graph is well-known to be planar.
2. Planar embedding: Draw as nested squares (inner square inside outer square) with 4 edges connecting corresponding corners.

Answer for : Planar.

(Modified cube):

1. Analyze additions: The extra edges create more connectivity.
2. Search for subdivision:
   • Label vertices appropriately
   • Identify two sets of 3 vertices each: (red) and (blue)
   • Find paths connecting every to every
   • The extra diagonal and curved edge provide the necessary connections
3. Finding the subdivision:
   • The vertices can be partitioned to show 9 paths between two sets of 3
   • Some paths go through intermediate vertices (, ), which are subdivision points

Answer for : Not planar (contains a subdivision of ).

4.10. Chromatic Number of Bipartite Graph (Tutorial 11, Task 5)

What is the chromatic number of a bipartite graph with 8 vertices (4 on each side)?

Click to see the solution

Key Concept: Bipartite graphs are always 2-colourable.

1. Property of bipartite graphs: Vertices can be partitioned into two sets where edges only go between sets, not within sets.
2. Colouring strategy:
   • Assign colour 1 to all vertices in the left partition
   • Assign colour 2 to all vertices in the right partition
3. Verification: Since no edges exist within a partition, no two adjacent vertices share a colour.

Answer:

4.11. Chromatic Number of Pentagon (Tutorial 11, Task 6)

What is the chromatic number of a pentagon graph (cycle )?

Click to see the solution

Key Concept: Odd cycles require 3 colours; even cycles require 2 colours.

1. Structure: is a cycle with 5 vertices: A - B - C - D - E - A
2. Why 2 colours fail:
   • Start: A = colour 1
   • B is adjacent to A: B = colour 2
   • C is adjacent to B: C = colour 1
   • D is adjacent to C: D = colour 2
   • E is adjacent to D: E = colour 1
   • But E is also adjacent to A, and both have colour 1!
   • Contradiction: 2 colours insufficient.
3. 3-colouring works:
   • A = 1 (Red)
   • B = 2 (Green)
   • C = 1 (Red)
   • D = 2 (Green)
   • E = 3 (Blue) — need third colour since E is adjacent to both A (Red) and D (Green)

Answer:

4.12. Chromatic Number of (Tutorial 11, Task 7)

What is the chromatic number of the complete graph ?

Click to see the solution

Key Concept: In a complete graph, every vertex is adjacent to every other vertex.

1. Structure: has 4 vertices where every pair is connected.
2. Consequence: No two vertices can share a colour.
3. Required colours: Each of the 4 vertices needs a distinct colour.
4. Colouring:
   • Vertex A = colour 1 (Red)
   • Vertex B = colour 2 (Blue)
   • Vertex C = colour 3 (Green)
   • Vertex D = colour 4 (Yellow)

Answer:

4.13. Chromatic Number of Wheel Graph (Tutorial 11, Task 8)

What is the chromatic number of a wheel graph (a cycle of 7 vertices with a central hub connected to all of them)?

Click to see the solution

Key Concept: A wheel graph consists of an outer cycle plus a central hub connected to all cycle vertices.

1. Structure of :
   • Outer cycle: 7 vertices (odd cycle)
   • Central hub: 1 vertex connected to all 7 outer vertices
   • Total: 8 vertices
2. Attempt with 3 colours:
   • The outer cycle is an odd cycle, requiring 3 colours
   • Colour the outer vertices: 1, 2, 1, 2, 1, 2, 3 (the 7th vertex must differ from both the 6th and the 1st)
   • So outer cycle uses colours {1, 2, 3}
   • The central hub is adjacent to ALL outer vertices, including vertices of colours 1, 2, and 3
   • Therefore, the hub needs a 4th colour!
3. 4-colouring works:
   • Outer cycle: colours 1, 2, 3 distributed (e.g., 1, 2, 1, 2, 1, 2, 3)
   • Central hub: colour 4

Answer: